﻿#include <iostream>

static bool findElement(int* matrix, int colSize, int rowSize, int target)
{
    int x = colSize - 1;
    int y = 0;
    while (x >= 0 && y < rowSize)
    {
        int cur = matrix[x + y * colSize];
        if (cur == target)
        {
            printf("target in (%d,%d)\n", x, y);
            return true;
        }

        if (cur > target)
        {
            --x;
        }
        else
        {
            ++y;
        }
    }

    return false;
}

/**
 * 给定一个元素为非负整数的二维数组matrix，每行和每列都是从小到大有序的，
 * 再给定一个非负整数aim，请判断aim是否在matrix中。
 *
 * 例如：
 *
 *   1  5  9  10
 *   2  6  11 13
 *   7  9  15 17
 *
 *  请找到7。
 *  思路：从右上角开始搜索。
 *  1. 10>7, ∴10下方的元素不要了，往左走。
 *  2. 9>7, ∴9下方的元素不要了，往左走。
 *  3. 5<7, ∴5左方的元素肯定也小于7，不要了，往下走。
 *  4. 6<7, ∴6左方的元素不要了，往下走。
 *  5. 9>7, 往左走。
 *  6. 找到了
 */
int main_NumberExistsInSortedMatrix()
{
    int colSize = 4;
    int matrix[] = {
        1,5,9,10,
        2,6,11,13,
        7,9,15,17,
    };

    int rowSize = sizeof(matrix) / (sizeof(int) * colSize);
    int target = 7;
    printf("find result: %d\n", findElement(matrix, colSize, rowSize, target));

    return 0;
}